package leetcode

// validPathDfs 使用深度优先搜索算法来判断图中是否存在从 target 到 destination 的有效路径。
// 参数:
//
//	n - 图中节点的数量。
//	edges - 图的边，每个元素是一个包含两个节点的数组，表示这两个节点之间有边相连。
//	target - 起始节点。
//	destination - 目标节点。
//
// 返回值:
//
//	如果存在从 target 到 destination 的路径，返回 true；否则返回 false。
func validPathDfs(n int, edges [][]int, source int, destination int) bool {
	// 如果起始节点和目标节点相同，则无需搜索，直接返回 true。
	if source == destination {
		return true
	}

	// 如果节点数量为 0 或边的列表为空，则无法存在路径。
	if n == 0 || len(edges) == 0 {
		return false
	}

	// 构建图的邻接表表示。
	graph := make([][]int, n)
	for _, edge := range edges {
		begin := edge[0]
		end := edge[1]
		graph[begin] = append(graph[begin], end)
		graph[end] = append(graph[end], begin)
	}

	// 使用一个数组来记录节点是否被访问过。
	visited := make([]bool, n)
	// 从起始节点开始进行深度优先搜索。
	return dfs(source, destination, graph, visited)
}

// dfs 是深度优先搜索的递归函数，用于查找是否存在从当前节点到目标节点的路径。
// 参数:
//
//	cur - 当前正在访问的节点。
//	destination - 目标节点。
//	graph - 图的邻接表表示。
//	visited - 记录每个节点是否被访问过的数组。
//
// 返回值:
//
//	如果存在从当前节点到目标节点的路径，返回 true；否则返回 false。
func dfs(cur, destination int, graph [][]int, visited []bool) bool {
	// 如果当前节点已经被访问过，则返回 false，避免循环。
	if visited[cur] {
		return false
	}
	visited[cur] = true

	// 如果当前节点是目标节点，则返回 true。
	if cur == destination {
		return true
	}

	// 遍历当前节点的所有邻接节点，递归进行深度优先搜索。
	for _, next := range graph[cur] {
		if dfs(next, destination, graph, visited) {
			return true
		}
	}

	return false
}
